package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author shkstart
 * @create 2021-08-19 17:28
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
//        shellSort2(arr);
//        System.out.println(Arrays.toString(arr));
//        int[] arr ={3,9,-1,10,-2};
//        int[] arr = new int[80000];
//        for (int i=0;i<80000;i++){
//            arr[i]=(int)(Math.random()*800000);
//        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date1);
        System.out.println("排序前的时间="+format);

       shellSort2(arr);
//        System.out.println(Arrays.toString(arr));
        Date date2 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format2 = simpleDateFormat.format(date2);
        System.out.println("排序后的时间="+format2);
    }
    //希尔排序
    public static void shellSort(int[] arr){
        int temp=0;
        //统计第几轮
        int count=0;
        //每一轮需要几组
        for (int gap=arr.length/2;gap>0;gap/=2){
            //一组中有几个元素
            for (int i=gap;i<arr.length;i++){
                //交换元素的坐标
                for (int j=i-gap;j>=0;j-=gap){
                    if (arr[j]>arr[j+gap]){
                        temp=arr[j];
                        arr[j]=arr[j+gap];
                        arr[j+gap]=temp;
                    }
                }
            }
//            System.out.println("希尔排序"+(++count)+"轮"+ Arrays.toString(arr));
        }

    }
    //新的位移方法
//    public static void shellSort2(int[] arr){
//        for (int gap=arr.length/2;gap>0;gap/=2){
//            for (int i=gap;i<arr.length;i++){
//          //转移参数
//                int j=i;
//                //保存变量
//                int temp=arr[j];
//                //需要位移的条件
//                if (arr[j]<arr[j-gap]){
//                    //位移到那一步
//                    //实际本质就是交换
//                    while (j-gap>=0&&arr[j-gap]>temp){
//                        //后面的赋值给前面
//                        arr[j]=arr[j-gap];
//                        j-=gap;
//
//                    }
//
//                        arr[j] = temp;
//                }
//
//            }
//        }
//    }
    public static void shellSort2(int[] arr){
        int j;
        for (int grap=arr.length/2;grap>0;grap/=2){
            for (int i=grap;i<arr.length;i++){
                int temp=arr[i];
                for ( j=i;j>=grap&&temp<arr[j-grap];j-=grap){
                    arr[j]=arr[j-grap];
                }
                arr[j]=temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

}
